package algorithm.leetcode;

import java.util.Arrays;

public class NO88_合并两个有序数组 {

    public static void main(String[] args) {
        int[] num1 = {1, 2, 3, 0, 0, 0};
        int[] num2 = {2, 5, 6};
        new Solution().merge(num1, 3, num2, 3);
        System.out.println(Arrays.toString(num1));
    }

    static class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int index = 0, i = 0;
            while (index < m + n) {
                // index-i的含义是num1中剩余的元素个数。
                int a = index - i < m ? nums1[index] : Integer.MAX_VALUE;
                int b = i < n ? nums2[i] : Integer.MAX_VALUE;
                if (b < a) {
                    // 替换的时候对数组进行后移操作
                    for (int j = nums1.length - 1; j > index; j--) {
                        nums1[j] = nums1[j - 1];
                    }
                    nums1[index] = b;
                    i++;
                }
                index++;
            }
        }
    }

    static class Solution2022 {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int indexM = 0, indexN = 0;
            int count = 0;
            int[] tool = Arrays.copyOf(nums1, m);

            while (indexM < m || indexN < n) {
                int numA = (indexM < m) ? tool[indexM] : (int) 1e9;
                int numB = (indexN < n) ? nums2[indexN] : (int) 1e9;
                if (numA < numB) {
                    nums1[count] = numA;
                    count++;
                    indexM++;
                } else if (numA > numB) {
                    nums1[count] = numB;
                    count++;
                    indexN++;
                } else {
                    indexM++;
                    indexN++;
                    for (int i = 0; i < 2; i++) {
                        nums1[count] = numA;
                        count++;
                    }
                }
            }

        }
    }
}
